/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package pkg8puzzle;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 *
 * @author LENON
 */
public class Puzzle8 {
    private int[][] inicial;
    private int[][] objetivo;
    private List<Node> open = new ArrayList<Node>();
    private List<Node> closed = new ArrayList<Node>();
    private int h = 2; //Seleciona a Heuristica: 1(peças fora do lugar) ou 2(Manhattan)
    private int ACABOU = 0;
    
    public Puzzle8(int[][] matrizinicial, int[][] matrizfinal) {
        inicial = matrizinicial;
        objetivo = matrizfinal;
    }
    
    public void Iniciar()
    {
        int eficiencia = 0;
        Node atual;
        int hAux;
        System.out.println("Estado Inicial:");
        imprimirJogo(inicial);
        
        // Nó Raiz em OPEN:
        hAux = calculaH(inicial);
        Node raiz = new Node(inicial, hAux, 0);
        open.add(raiz);
        while(ACABOU==0)
        {
            
            ordenaOpen();
            atual = pegaPrimeiro();

            if (!acabou(atual.getEstado()))
            {
            geraOpen(atual);
            }
            eficiencia++;
            if(ACABOU==1){
                imprimirCaminho(atual);
          //  imprimirOpen();
           // imprimirClosed();
          //  System.out.println("-------");
           // imprimirJogo(atual.getEstado());
           // System.out.println("-------");
            System.out.println("---FINAL----");
            imprimirJogo(atual.getEstado());
            System.out.println("F(x)="+atual.getF());
            System.out.println("Eficiência:"+eficiencia);
            System.out.println("-------");
                    }
        }
       
        
    }
    public void imprimirCaminho(Node atual){
        System.out.println("---CAMINHO: TAMANHO="+(atual.caminho.size()-1)+"----");
        for(Node no:atual.caminho){
            imprimirJogo(no.getEstado());
            System.out.println("F(x)="+no.getF());
            System.out.println("Heuristica="+no.getHeuristica());
            System.out.println("-------");
        }
        
    }
    public void imprimirClosed(){
        System.out.println("---CLOSED----");
        for(Node fechado: closed){
                        
            imprimirJogo(fechado.getEstado());
            System.out.println("F(x)="+fechado.getF());
            System.out.println("Heuristica="+fechado.getHeuristica());
            System.out.println("-------");
        }
    }
        public void imprimirOpen(){
        System.out.println("---OPEN----");
        for(Node aberto: open){
                        
            imprimirJogo(aberto.getEstado());
            System.out.println("F(x)="+aberto.getF());
            System.out.println("Heuristica="+aberto.getHeuristica());
            System.out.println("-------");
        }
    }
    public boolean comparaOpen(Node atual){
        int index=0;
        boolean igual = true;
        int[][]m1 = atual.getEstado();
        for(Node aberto: open){
            igual = true;
            for(int linha=0; linha<3;linha++){
            for(int coluna=0;coluna<3;coluna++){ 
                if (m1[linha][coluna]!=aberto.getEstado()[linha][coluna]){
                    igual = false;
                }
            }
            
            }
            if(igual){
                if(atual.getF()<aberto.getF()){
                   open.remove(aberto);
                return true;
                }else{
                    return false;
                }
            }
               
            
            index++;
    }
        return true;
    }   
    public boolean comparaClosed(Node atual){
        int index=0;
        boolean igual = true;
        int[][]m1 = atual.getEstado();
        for(Node fechado: closed){
            igual = true;
            for(int linha=0; linha<3;linha++){
            for(int coluna=0;coluna<3;coluna++){ 
                if (m1[linha][coluna]!=fechado.getEstado()[linha][coluna]){
                    igual = false;
                }
            }
            
            }
            if(igual){
                if(atual.getF()<fechado.getF()){
                   closed.remove(fechado);
                return true;
                }else{
                    return false;
                }
            }
               
            
            index++;
    }
        return true;
    } 
    public boolean acabou(int[][] atual){
        
        for(int linha=0; linha<3;linha++){
            for(int coluna=0;coluna<3;coluna++){ 
                if(atual[linha][coluna]!=objetivo[linha][coluna]){
                    return false;
                    
                }
            }
        }
        ACABOU = 1;
        return true;
    }
    
    public void geraOpen(Node atual)
    {
        int[][] estadoAux = new int[3][3];
        int[] posicaoAux = new int[2];
        int valorAux;
        int gAux, hAux;
        int posicaoZero[] = new int[2];
        int[][] estadoAtual = atual.getEstado();
        open.remove(atual);
        closed.add(atual);
        posicaoZero = getValor(estadoAtual, 0);
        gAux = atual.getG() + 1;
        if((posicaoZero[0]==0)&&(posicaoZero[1]==0))
        {
            // 0 X X
            // X X X
            // X X X
            //1a Jogada possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 0;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            Node aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
         
            // 2a Jogada Possivel:
            posicaoAux[0] = 0;
            posicaoAux[1] = 1;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
        }
        
        if((posicaoZero[0]==2)&&(posicaoZero[1]==0))
        {
            // X X X
            // X X X
            // 0 X X
            //1a Jogada possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 0;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            Node aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                   
                   open.add(aux);
                   }
            }
            // 2a Jogada Possivel:
            posicaoAux[0] = 2;
            posicaoAux[1] = 1;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                   
                   open.add(aux);
                   }
            }
        }
        if((posicaoZero[0]==0)&&(posicaoZero[1]==2))
        {
            // X X 0
            // X X X
            // X X X
            //1a Jogada possivel:
            posicaoAux[0] = 0;
            posicaoAux[1] = 1;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            Node aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                   
                   open.add(aux);
                   }
            }
            // 2a Jogada Possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 2;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                   
                   open.add(aux);
                   }
            }
        }
        if((posicaoZero[0]==2)&&(posicaoZero[1]==2))
        {
            // X X X
            // X X X
            // X X 0
            //1a Jogada possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 2;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            Node aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                   
                   open.add(aux);
                   }
            }
            // 2a Jogada Possivel:
            posicaoAux[0] = 2;
            posicaoAux[1] = 1;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux)){
                   
                   open.add(aux);
                   }
            }
            
        }
        if((posicaoZero[0]==1)&&(posicaoZero[1]==1))
        {
            // X X X
            // X 0 X
            // X X X
             //1a Jogada possivel:           
            posicaoAux[0] = 0;
            posicaoAux[1] = 1;

            estadoAux=swap(estadoAtual, posicaoZero, posicaoAux);;
            Node aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 2a Jogada Possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 0;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 3a Jogada Possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 2;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 4a Jogada Possivel:
            posicaoAux[0] = 2;
            posicaoAux[1] = 1;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
        }
        
        if((posicaoZero[0]==0)&&(posicaoZero[1]==1))
        {
            // X 0 X
            // X X X
            // X X X
            //1a Jogada possivel:
            posicaoAux[0] = 0;
            posicaoAux[1] = 0;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            Node aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
           if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 2a Jogada Possivel:
            posicaoAux[0] = 0;
            posicaoAux[1] = 2;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 3a Jogada Possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 1;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
        }
        
        if((posicaoZero[0]==2)&&(posicaoZero[1]==1))
        {
            // X X X
            // X X X
            // X 0 X
                     //1a Jogada possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 1;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            Node aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 2a Jogada Possivel:
            posicaoAux[0] = 2;
            posicaoAux[1] = 0;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 3a Jogada Possivel:
            posicaoAux[0] = 2;
            posicaoAux[1] = 2;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
        }
          if((posicaoZero[0]==1)&&(posicaoZero[1]==0))
        {
            // X X X
            // 0 X X
            // X X X
            //1a Jogada possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 1;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            Node aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 2a Jogada Possivel:
            posicaoAux[0] = 0;
            posicaoAux[1] = 0;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
           if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 3a Jogada Possivel:
            posicaoAux[0] = 2;
            posicaoAux[1] = 0;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
        }
            if((posicaoZero[0]==1)&&(posicaoZero[1]==2))
        {
            // X X X
            // X X 0
            // X X X
            //1a Jogada possivel:
            posicaoAux[0] = 0;
            posicaoAux[1] = 2;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            Node aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 2a Jogada Possivel:
            posicaoAux[0] = 2;
            posicaoAux[1] = 2;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
            // 3a Jogada Possivel:
            posicaoAux[0] = 1;
            posicaoAux[1] = 1;
            estadoAux=swap(estadoAtual.clone(), posicaoZero, posicaoAux);
            aux = new Node(estadoAux, calculaH(estadoAux),gAux,atual.caminho);
            if (comparaClosed(aux))
            {
                   if(comparaOpen(aux))
                   {
                       
                   open.add(aux);
                   }
            }
        }
        
    }
    
    public int[][] swap(int[][]m,int[] p1,int[] p2){

        int temp=0;
        int[][]matriz = new int[3][3];
        for(int linha=0; linha<3;linha++){
            for(int coluna=0;coluna<3;coluna++){
                    matriz[linha][coluna]=m[linha][coluna];
                }
        }
        matriz[p1[0]][p1[1]] =matriz[p2[0]][p2[1]];
        matriz[p2[0]][p2[1]] = temp;
        return matriz;
        
    }
    
    public int[] getValor(int[][] valor, int alvo){
        int local[] = new int[2];
        
        
        for(int linha=0; linha<3;linha++){
            for(int coluna=0;coluna<3;coluna++){
                if(valor[linha][coluna]==alvo){
                    local[0]=linha;
                    local[1]=coluna;
                }
            }
        }
       return  local;
    }

    public void ordenaOpen()
    {
        Collections.sort (open, new Comparator() {  
            public int compare(Object o1, Object o2) {  
                Node p1 = (Node) o1;  
                Node p2 = (Node) o2;  
                return p1.getF() < p2.getF() ? -1 : (p1.getF() > p2.getF() ? +1 : 0);  
            }  
        });
    }
    
    public Node pegaPrimeiro()
    {
        
        Node e = new Node();
        e = open.get(0);
        e.caminho.add(e);
        return e;
    }
    
    public void testaOBJ(int[][] atual)
    {
        int i, k, contador;
        contador=0;
        for (i=0; i<3; i++)
        {
            for(k=0;k<3;k++)
            {
                if (atual[i][k]==objetivo[i][k])
                {
                    contador++;
                }
            }
        }
        if (contador==9)
        {
            ACABOU = 1;
        }
    }
    
    public void imprimirJogo(int[][] jogo)
    {
        int i,k;
        for (i=0; i<3; i++)
        {
            for (k=0; k<3; k++)
            {
                System.out.print(jogo[i][k]);
            }
                System.out.print("\n");
        }
        
    }
    public int calculaH(int[][] atual){
        switch(h){
            case 1:
                return calculaH1(atual);
            case 2:
                return calculaH2(atual);
        }
        return 1;
    }
    public int calculaH1(int[][] atual) // Heuristica de numero de pecas fora do lugar
    {
        int h1, i, k;
        h1 = 0;
        for (i=0; i<3; i++)
        {
            for (k=0;k<3;k++)
            {
                if (atual[i][k]!=objetivo[i][k])
                        {
                            h1++;
                        }
            }
        }
        return h1;
    }
    
    public int calculaH2(int[][] matrizAt){ // Heuristica Distancia de Manhatan
        int h=0;
        int objetivos[] = new int[2];
            for(int linha=0; linha<3;linha++){
            for(int coluna=0;coluna<3;coluna++){
                  objetivos = getValor(objetivo, matrizAt[linha][coluna]);
                 
                  h += Math.abs(objetivos[0]-linha) + Math.abs(objetivos[1]-coluna);
            }
            }
        return h;
        
    }
}

